import sys
from typing import List


class Solution01:

    # 超时
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        min_value = 10 ** 4
        value = 0
        for index01 in range(len(nums[:-2])):
            for index02 in range(index01 + 1, len(nums[:-1])):
                for index03 in range(index02 + 1, len(nums)):
                    sum = nums[index01] + nums[index02] + nums[index03]
                    temp = target - sum
                    if abs(temp) < min_value:
                        min_value = abs(temp)
                        value = sum
        return value


    def threeSumClosest02(self, nums: List[int], target: int) -> int:
        nums.sort()
        road = sys.maxsize

        value = 0

        for first in range(len(nums) - 2):
            second = first + 1
            third = len(nums) - 1
            while third > second:
                roadDemo = abs(target - nums[first] - nums[second] - nums[third])
                if road > roadDemo:
                    road = roadDemo
                    value = nums[first] + nums[second] + nums[third]
                if nums[first] + nums[second] + nums[third] > target:
                    third = third - 1
                elif nums[first] + nums[second] + nums[third] - target < 0:
                    second = second + 1
                else:
                    return target
        return value


if __name__ == "__main__":
    nums = [-1000,-1000,-1000]
    target = 10000
    solution = Solution01()
    print(solution.threeSumClosest02(nums, target))